package ru.ifmo.automaton;

import java.util.*;

/**
 * @author avhaliullin
 */
public class SynchronizingAutomatonImpl<C, S> extends AutomatonImp<C, S> implements SynchronizingAutomaton<C, S> {
    private final int mswLength;

    public SynchronizingAutomatonImpl(Map<S, Map<C, S>> transitions, Set<S> terminalStates, S initialState, S failState, List<C> alphabet, int mswLength) {
        super(transitions, terminalStates, initialState, failState, alphabet);
        this.mswLength = mswLength;
    }

    public SynchronizingAutomatonImpl(Map<S, Map<C, S>> transitions, Set<S> terminalStates, S initialState, S failState, List<C> alphabet) {
        super(transitions, terminalStates, initialState, failState, alphabet);
        this.mswLength = computeMSWLength();
        goToState(initialState);
    }

    private int computeMSWLength() {
        Queue<Set<S>> stateSets = new ArrayDeque<Set<S>>();
        Queue<Integer> length = new ArrayDeque<Integer>();
        Set<Set<S>> processedStateSets = new HashSet<Set<S>>(1 << getStatesCount());

        Set<S> initialStateSet = new AbstractSet<S>() {
            @Override
            public Iterator<S> iterator() {
                return SynchronizingAutomatonImpl.this.iterator();
            }

            @Override
            public int size() {
                return getStatesCount();
            }
        };
        stateSets.add(initialStateSet);
        length.add(0);

        while (stateSets.peek().size() > 1) {
            Set<S> currentSet = stateSets.poll();
            int currentLength = length.poll();

            for (C symbol : getAlphabet()) {
                Set<S> stepFromCurrent = new HashSet<S>();
                for (S state : currentSet) {
                    goToState(state);
                    stepFromCurrent.add(step(symbol));
                }
                if (processedStateSets.add(stepFromCurrent)) {
                    stateSets.add(stepFromCurrent);
                    length.add(currentLength + 1);
                }
            }

            if (stateSets.isEmpty()) {
                throw new RuntimeException("Automaton is not synchronizing!");
            }
        }
        return length.poll();
    }

    public int mswLength() {
        return mswLength;
    }
}
